package com.xxd.algo.newcode.mid01.class05;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Code04_TopKTimesRealTime {

    public static class Node {
        public String str;
        public int times;

        public Node(String s, int t) {
            str = s;
            times = t;
        }

		@Override
		public String toString() {
			return "Node{" +
					"str='" + str + '\'' +
					", times=" + times +
					'}';
		}
	}

    public static class TopKRecord {
        private Node[] heap;
        private int heapSize;
        private HashMap<String, Node> strNodeMap;
        private HashMap<Node, Integer> nodeIndexMap;


        public TopKRecord(int K) {
            heap = new Node[K];
            heapSize = 0;
            strNodeMap = new HashMap<String, Node>();
            nodeIndexMap = new HashMap<Node, Integer>();
        }

        public void add(String str) {
            Node curNode = null;
            int preIndex = -1; // str之前在堆上的位置
            if (!strNodeMap.containsKey(str)) {
                curNode = new Node(str, 1);
                strNodeMap.put(str, curNode);
                nodeIndexMap.put(curNode, -1);
            } else {
                curNode = strNodeMap.get(str);
                curNode.times++;
                preIndex = nodeIndexMap.get(curNode); // 在堆中的位置
            }

            if (preIndex == -1) { // 不在堆上
                if (heapSize == heap.length) { // 堆满了
                    if (heap[0].times < curNode.times) { // 看下门槛够不够，够门槛了。踢出一个，加入一个，踢出的就是门槛就是头
                        nodeIndexMap.put(heap[0], -1);
                        nodeIndexMap.put(curNode, 0);
                        heap[0] = curNode;
                        heapify(0, heapSize); // 调整堆
                    }
                } else { // 堆没有满，直接进入
                    nodeIndexMap.put(curNode, heapSize);
                    heap[heapSize] = curNode;
                    heapInsert(heapSize++);
                }
            } else { // 已经在堆上了
                heapify(preIndex, heapSize);
            }
        }

        public void printTopK() {
            System.out.println("TOP: ");
            for (int i = 0; i != heap.length; i++) {
                if (heap[i] == null) {
                    break;
                }
                System.out.print("Str: " + heap[i].str);
                System.out.println(" Times: " + heap[i].times);
            }
        }

        private void heapInsert(int index) {
            while (index != 0) {
                int parent = (index - 1) / 2;
                if (heap[index].times < heap[parent].times) {
                    swap(parent, index);
                    index = parent;
                } else {
                    break;
                }
            }
        }

        private void heapify(int index, int heapSize) {
            int l = index * 2 + 1;
            int r = index * 2 + 2;
            int smallest = index;
            while (l < heapSize) {
                if (heap[l].times < heap[index].times) {
                    smallest = l;
                }
                if (r < heapSize && heap[r].times < heap[smallest].times) {
                    smallest = r;
                }
                if (smallest != index) {
                    swap(smallest, index);
                } else {
                    break;
                }
                index = smallest;
                l = index * 2 + 1;
                r = index * 2 + 2;
            }
        }

        private void swap(int index1, int index2) {
            nodeIndexMap.put(heap[index1], index2);
            nodeIndexMap.put(heap[index2], index1);
            Node tmp = heap[index1];
            heap[index1] = heap[index2];
            heap[index2] = tmp;
        }

    }

    public static String[] generateRandomArray(int len, int max) {
        String[] res = new String[len];
        for (int i = 0; i != len; i++) {
            res[i] = String.valueOf((int) (Math.random() * (max + 1)));
        }
        return res;
    }

    public static void printArray(String[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
		TopKRecord record = new TopKRecord(2);
		record.add("zuo");
		record.printTopK();
		record.add("cheng");
		record.add("cheng");
		record.printTopK();
		record.add("Yun");
		record.add("Yun");
		record.printTopK();


		int[] arr = {1, 4, 5, 3, 6, 7, 9, 8};

		Node a = new Node("a",3);
		Node b = new Node("b",4);
		Node c = new Node("c",5);
		Node d = new Node("d",1);
		Node g = new Node("g", 7);

		Node[] nodes = {
				a,b,c,d,g
		};

		PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {

			@Override
			public int compare(Node o1, Node o2) {
				return o1.times - o2.times;
			}
		});

		for (Node node : nodes) {
			queue.add(node);
		}

		while (!queue.isEmpty()) {
			System.out.println(queue.poll());
		}


		for (Node node : nodes) {
			queue.add(node);
		}

		System.out.println("===========");
		b.times = -1;

		while (!queue.isEmpty()) {
			System.out.println(queue.poll());
		}
	}
}